set associative cache

    A compromise between a direct mapped cache
   and a fully associative cache where each address is mapped
   to a certain set of cache locations.  The address space is
   divided into blocks of 2^m bytes (the cache line size),
   discarding the bottom m address bits.  An "n-way set
   associative" cache with S sets has n cache locations in each
   set.  Block b is mapped to set "b mod S" and may be stored in
   any of the n locations in that set with its upper address bits
   as a tag.  To determine whether block b is in the cache, set
   "b mod S" is searched associatively for the tag.

   A direct mapped cache could be described as "one-way set
   associative", i.e. one location in each set whereas a fully
   associative cache is N-way associative (where N is the total
   number of blocks in the cache).  Performance studies have
   shown that it is generally more effective to increase the
   number of entries rather than associativity and that 2- to
   16-way set associative caches perform almost as well as fully
   associative caches at little extra cost over direct mapping.

   (2004-10-18)